package 剑指offer.demo4;
//https://www.nowcoder.com/practice/a861533d45854474ac791d90e447bafd?
/*
注意边界值处理
 */
public class 二叉搜索树的后序遍历序列 {
    public boolean VerifySquenceOfBST(int [] sequence) {
        //合法性判断
        if (sequence.length == 0){
            return false;
        }
        return help(sequence , 0 , sequence.length - 1);
    }
    //给定数组及其边界判断是否满足后序遍历结果
    public boolean help(int[] arr , int start , int end){
        //当区间空了时说明所有之前我们处理的数据都满足二叉搜索树结果，当然也是判出条件
        if (start >= end){
            return true;
        }
        //后序遍历最后一个就是树根
        int root = arr[end];
        //处理左子树情况
        int i = start;
        while (i < end && arr[i] < root){
            i ++;
        }
        //此时说明遇到了大于root的值，该开始处理又子树了
        for (int j = i; j < end ; j++) {
            if (arr[j] < root)
                return false;
        }
        //走到这里说明这个大树满足二叉搜索树条件，继续递归判断其左右子树是否也满足条件就好了
        //左：start ～ i - 1；右：i ～ end - 1
        return help(arr , start , i - 1) && help(arr , i , end - 1);
    }
}
